import java.util.*;

public class MyBinaryTree {
    static class BTNode {
        private int val;
        private BTNode left;
        private BTNode right;

        public BTNode(int val) {
            this.val = val;
        }
    }

    public BTNode root;

    public void createBinaryTree() {
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);
        root = node1;
        node1.right = node3;
        node1.left = node2;
        node2.left = node4;
        node3.left = node5;
        node3.right = node6;
    }

    public static BTNode createBinaryTree1() {
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(2);
        BTNode node4 = new BTNode(3);
        BTNode node5 = new BTNode(3);
        BTNode node6 = new BTNode(4);
        BTNode node7 = new BTNode(4);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node4.left = node6;
        node5.right = node7;
        return node1;
    }
    //前序遍历
    public void preOrder(BTNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历
    public void inOrder(BTNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    //后序遍历
    public void postOrder(BTNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    //获取二叉树中节点的个数
    public int size(BTNode root) {
        if (root == null) {
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }

    //获取叶子节点的个数
    public int getLeafSize(BTNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafSize(root.left) + getLeafSize(root.right);
    }

    //求取二叉树的深度
    public static int getHeight(BTNode root) {
        if (root == null) {
            return 0;
        }
        int leftSize = getHeight(root.left);
        int rightSize = getHeight(root.right);
        int max = (leftSize > rightSize) ? (leftSize + 1) : (rightSize + 1);
        return max;
    }

    //求二叉树第k层节点的个数 = 该树的左子树的k-1节点个数 + 该树的右子树的k-1节点个数
    public int getLevelNodeCount(BTNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getLevelNodeCount(root.left, k - 1) + getLevelNodeCount(root.right, k - 1);
    }

    //判断val值是否存在于二叉树中
    public BTNode find(BTNode root, int val) {
        if (root == null) {
            return root;
        }
        if (root.val == val) {
            return root;
        }
        BTNode ret1 = find(root.left, val);
        if (ret1 != null) {
            return ret1;
        }
        BTNode ret2 = find(root.right, val);
        if (ret2 != null) {
            return ret2;
        }
        return null;
    }

    public boolean isSameTree(BTNode p, BTNode q) {
        //一个为空一个不为空
        if ((p != null && q == null) || (p == null && q != null)) {
            return false;
        }
        //两个二叉树都为空
        if (p == null && q == null) {
            return true;
        }
        //根节点不相同
        if (p.val != q.val) {
            return false;
        }
        //根节点相同且p，q不相同，接下来判断子树是否相等 ==> 只有左右子树都相同的时候此时整个二叉树才相等
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    public boolean isSubtree(BTNode root, BTNode subRoot) {
        //不加的话会出现空指针异常，原因：root可能为null解引用是就会出现该异常
        if(root == null || subRoot == null) {
            return false;
        }
        if(isSameTree(root, subRoot)) {
            return true;
        }
        if(isSubtree(root.left, subRoot)) {
            return true;
        }
        if(isSubtree(root.right, subRoot)) {
            return true;
        }

        return false;
    }

    public BTNode invertTree(BTNode root) {
        if(root == null) {
            return root;
        }
        BTNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public boolean isCom(BTNode root) {
        if(root == null) {
            return true;
        }
        Queue<BTNode> q = new LinkedList<>();
        q.offer(root);
        while(q.peek() != null) {
            BTNode cur = q.poll();
            q.offer(cur.left);
            q.offer(cur.right);
        }
        while(!q.isEmpty()) {
            if(q.poll() != null) {
                return false;
            }
        }
        return true;
    }

    //
    public List<Integer> preorderTraversal(BTNode root) {

        List<Integer> l = new ArrayList<>();
        Stack<BTNode> stack = new Stack<>();
        if(root == null) {
            return l;
        }
        BTNode cur = root;
        while(cur != null || !stack.empty())
        {
            while(cur != null) {
                stack.push(cur);
                l.add(cur.val);
                cur = cur.left;
            }
            BTNode top = stack.pop();
            cur = top.right;
        }
        return l;
    }


    public String tree2str(BTNode root) {
        StringBuilder str = new StringBuilder();
        tree2strChild(root, str);
        return str.toString();
    }
    public void tree2strChild(BTNode root, StringBuilder str) {
        if(root == null) {
            return;
        }
        str.append(root.val);
        if(root.left != null) {
            str.append("(");
            tree2strChild(root.left, str);
            str.append(")");
        }else {
            if(root.left != null) {
                str.append("()");
            }else {
                return;
            }
        }
        if(root.right != null) {
            str.append("(");
            tree2strChild(root.right, str);
            str.append(")");
        }else {
            return;
        }
    }

    public BTNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild1(preorder, inorder, 0, inorder.length - 1);
    }

    public int preindex;

    private int findRootIndex1(int[] preorder, int[] inorder, int preindex , int inbgin, int inend) {
        for(int i = inbgin; i <= inend; i++) {
            if(preorder[preindex] == inorder[i]) {
                return i;
            }
        }
        return -1;

    }
    private BTNode buildTreeChild1(int[] preorder, int[] inorder, int inbegin, int inend) {
        if(inbegin > inend) {
            return null;
        }
        BTNode node = new BTNode(preorder[preindex]);


        int rootindex = findRootIndex1(preorder, inorder, preindex, inbegin, inend);
        if(rootindex == -1) {
            return null;
        }
        preindex++;
        node.left = buildTreeChild1(preorder, inorder, inbegin, rootindex - 1);
        node.right = buildTreeChild1(preorder, inorder, rootindex + 1, inend);
        return node;
    }

    //中序和后序构造一颗二叉树
    public static int postIndex;
    public static BTNode buildTree2(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1; //后序遍历也可以确定根节点
        return buildTreeChild2(postorder, inorder, 0, inorder.length - 1, postIndex);
    }
    public static int findRootIndex2(int[] postorder, int[] inorder, int inbegin, int inend, int postIndex) {
        for(int i = inbegin; i <= inend; i++) {
            if(postorder[postIndex] == inorder[i]) {
                return i;
            }
        }
        return -1;

    }

    public static BTNode buildTreeChild2(int[] postorder, int[] inorder, int inbegin, int inend, int postIndex) {
        if(inbegin > inend) {
            return null;
        }
        BTNode root = new BTNode(postorder[postIndex]);

        int rootIndex = findRootIndex2(postorder, inorder, inbegin, inend, postIndex);
        if(rootIndex == -1) {
            return null;
        }
        postIndex--;

        root.right = buildTreeChild2(postorder, inorder, rootIndex + 1, inend, postIndex);
        root.left = buildTreeChild2(postorder, inorder, inbegin, rootIndex - 1, postIndex);

        return root;
    }
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }


    public static int i;
    private static TreeNode createTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        } else {
            i++;
        }
        return root;
    }
    private static void inOrder1(TreeNode root) {
        if(root == null) {
            return;
        }

        inOrder1(root.left);
        System.out.print(root.val + " ");
        inOrder1(root.right);
    }
    public static boolean isBalanced(BTNode root) {
        if(root == null) {
            return true;
        }

        int leftTree = getHeight1(root.left);
        int rightTree = getHeight1(root.right);
        if(Math.abs(leftTree - rightTree) <= 1) {
        return isBalanced(root.left) && isBalanced(root.right);
    }
        return false;

}
    public static int getHeight1(BTNode root) {
        if (root == null) {
            return 0;
        }
        int leftSize = getHeight1(root.left);
        int rightSize = getHeight1(root.right);
        int max = (leftSize > rightSize) ? (leftSize + 1) : (rightSize + 1);
        return max;
    }
    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//
//        while(scanner.hasNextLine()) {
//            String str = scanner.nextLine();
//            TreeNode root = createTree(str);
//            inOrder1(root);
//            System.out.println();
//        }
        BTNode root = createBinaryTree1();
        System.out.println(isBalanced(root));
//        System.out.println(isBalanced(root));

    }
}